﻿#include<iostream>
using namespace std;
// ⽤最新加了构造和析构的C++版本Stack实现
bool isValid(const char* s) {
	Stack st;
	while (*s)
	{
		if (*s == '[' || *s == '(' || *s == '{')
		{
			st.Push(*s);
		}
		else
		{
			// 右括号⽐左括号多，数量匹配问题
			if (st.Empty())
			{
				return false;
			}
			// 栈⾥⾯取左括号
			char top = st.Top();
			st.Pop();
			// 顺序不匹配
			if ((*s == ']' && top != '[')
				|| (*s == '}' && top != '{')
				|| (*s == ')' && top != '('))
			{
				return false;
			}
		}
		++s;
	}
	// 栈为空，返回真，说明数量都匹配 左括号多，右括号少匹配问题
	return st.Empty();
}
// ⽤之前C版本Stack实现
bool isValid(const char* s) {
	ST st;
	STInit(&st);
	while (*s)
	{
		// 左括号⼊栈
		if (*s == '(' || *s == '[' || *s == '{')
		{
			STPush(&st, *s);
		}
		else // 右括号取栈顶左括号尝试匹配
		{
			if (STEmpty(&st))
			{
				STDestroy(&st);
				return false;
			}
			char top = STTop(&st);
			STPop(&st);
			// 不匹配
			if ((top == '(' && *s != ')')
				|| (top == '{' && *s != '}')
				|| (top == '[' && *s != ']'))
			{
				STDestroy(&st);
				return false;
			}
		}
		++s;
	}
	// 栈不为空，说明左括号⽐右括号多，数量不匹配
	bool ret = STEmpty(&st);
	STDestroy(&st);
	return ret;
}